package C053;

import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * ClassName: C04
 * Package: C053
 * Description:
 *
 * @Author BCXJ
 * @Create 2025/4/8 11:40
 * @Version 1.0
 * @Since 1.0
 */
public class C04 {
    public static void main(String[] args) {
        //int[][] arr = {{1,0,1},{1,1,0},{1,1,0}};
        int[][] arr = {{0, 1, 1, 0}, {0, 1, 1, 1}, {1, 1, 1, 0}};
        System.out.println(numSubmat(arr));
    }

    static int MAXLEN = 150;
    static int[] count = new int[MAXLEN];
    static int m, n;

    static int size = 0;
    static int[] stack = new int[MAXLEN];

    public static int numSubmat(int[][] mat) {
        m = mat[0].length;
        n = mat.length;
        int ans = 0;
        for (int i = 0, j; i < n; i++) {
            for (j = 0; j < m; j++) {
                if (mat[i][j] == 0) {
                    count[j] = 0;
                } else {
                    count[j]++;
                }
            }
            ans += process();
        }

        return ans;
    }

    private static int process() {
        Arrays.fill(count, 0);
        int ans = 0;
        size = 0;
        int len, cmt, left;
        for (int i = 0; i < m; i++) {
            while (size > 0 && count[stack[size - 1]] >= count[i]) {
                if (count[stack[size - 1]] > count[i]) {
                    left = size - 2 < 0 ? -1 : stack[size - 2];
                    len = i - left - 1;
                    cmt = count[stack[size - 1]] - Math.max(left == -1 ? 0 : count[left], count[i]);
                    ans += cmt * (1 + len) * len / 2;
                }
                size--;
            }
            stack[size++] = i;
        }

        while (size > 0) {
            left = size - 2 == -1 ? -1 : stack[size - 2];
            len = m - left - 1;
            cmt = count[stack[size - 1]] - (left == -1 ? 0 : count[left]);
            ans += cmt * (1 + len) * len / 2;
            size--;
        }
        System.out.println(ans);
        return ans;
    }
}
